Change hash range reduction from remainder to multiplication
authorMattias Engdegård <mattiase@acm.org>
Mon, 15 Jan 2024 08:25:02 +0000 (09:25 +0100)
committerMattias Engdegård <mattiase@acm.org>
Tue, 6 Feb 2024 13:50:40 +0000 (14:50 +0100)
commite66870400d45e3d08265df9f6acd4631a5712139
treeca09e703762f4ebbdba620293e5265ea42b3016a
parentf6225d125c07bbde8c828b40eb6e81333e051c2a
Change hash range reduction from remainder to multiplication

This makes both lookups and rehashing cheaper.  The index vector size
is now always a power of 2.  The first table size is reduced to
6 (from 8), because index vectors would become excessively big
otherwise.

* src/lisp.h (struct Lisp_Hash_Table): Replace index_size with
index_bits.  All references adapted.
(hash_table_index_size): New accessor; use it where applicable.
* src/fns.c (hash_index_size): Replace with...
(compute_hash_index_bits): ...this new function, returning the log2 of the
index size.  All callers adapted.
(hash_index_index): Knuth multiplicative hashing instead of remainder.
(maybe_resize_hash_table): Reduce first table size from 8 to 6.
src/alloc.c
src/fns.c
src/lisp.h
src/pdumper.c